Data communication systems continue to require advanced methods of error detection of data being communicated over a noisy channel. Corrupted data or data having errors can be dealt with in many ways including correcting the error; in other cases retransmission of the data may be required. An integrated circuit including cyclic redundancy check (CRC) circuits have often been employed by communication systems to implement such error detection. One type of integrated circuit may include an integrated circuit having programmable logic, e.g., programmable logic devices (PLDs). PLDs are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of programmable tiles. The aim of an error detection technique is to enable the receiver of a message transmitted through a noisy (error-introducing) channel to determine whether the message has been corrupted. To do this, the transmitter constructs a value (called a checksum) that is a function of the message, and appends it to the message. The receiver can then use the same function to calculate the checksum of the received message and compare it with the appended checksum to see if the message was correctly received.
The basic idea of CRC algorithms is simply to treat the message as an enormous binary number, to divide it by another fixed binary number, and to make the remainder from this division the checksum. Upon receipt of the message, the receiver can perform the same division and compare the remainder with the “checksum” (transmitted remainder). One method of implementing a CRC is to utilize a serial process, e.g., using a linear feedback shift register (LFSR), in which single bits of a frame of data are accumulated one cycle at a time, to generate a frame check sequence (FCS) to be appended to the end of the data frame to be transmitted.
In order to accommodate large data frames or large system throughput requirements, the CRCs may be expanded from the ability to handle single bits of data at each clock cycle, to the ability to handle multiple data bits, or words, in a single clock cycle. In order to generate CRCs for data words having widths greater than one bit, however, a different CRC circuit is required for each data word width that is to be processed.
For example, communication protocols often utilize data packets having any number of data bytes. Given that each data byte represents 8 bits, therefore, performing CRC calculations on each data byte requires an 8-bit CRC circuit. In order to increase system throughput the data can be processed in parallel. For example, a system could process eight of the 8-bit data words at the same time resulting in a 64-bit datapath. Other examples include CRC communication protocols having data widths less than 8 bits, e.g., 5 bits. Should CRC calculations be required on larger data blocks, however, a possibility exists that an un-processed data residue whose width is smaller than the current CRC handling width would need to be included in the current CRC calculation.
In such an instance, multiple CRC blocks having multiple widths may be incorporated into the design to handle the data residue widths that may be possible. For example, if byte-wide data is processed 8 bytes at a time in parallel, then, in general, CRC blocks having widths of 56, 48, 40, 32, 24, 16, and 8 bits would be necessary to handle the data residue widths that may result during CRC processing. Such a design could be size prohibitive.
Furthermore, other examples exist where data is received having fixed widths, but real time CRC processing on the variable size data blocks is still required. In such an instance, a highly configurable CRC circuit would be necessary to handle a variety of data widths.
A cyclic redundancy check (CRC) is a type of function that takes an input data stream of a predetermined length per design specification or standard and produces an output value of a known size in accordance with the standard. A CRC can be used in the same way as a checksum to detect error of data during transmission or storage. CRCs are widely used due to the ease of implementation and the ease to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels (e.g., a wired transmission channel on a printed circuit board). Errors in both data transmission channels and magnetic storage media tend to be distributed non-uniformly (i.e., are “bursty”), making CRCs' properties more useful than alternative schemes such as multiple parity checks.
Various standards, such as Institute of Electrical and Electronics Engineers (IEEE) standards, have adopted various CRC polynomials, which made it challenging for designers to design a single CRC circuit adaptable to the various standards. This is important for a general-purpose device such as a PLD which may support different communication standards. Table 1 illustrates some of the popular polynomials used in CRC calculations.
TABLE 1NamePolynomialCRC-1x + 1 (use: hardware; also known as parity bit)CRC-5-ITUx5 + x4 + x2 + 1 (ITU G.704, p. 9)CRC-5-USBx5 + x2 + 1 (use: USB token packets)CRC-6-ITUx6 + x + 1 (ITU G.704, p. 3)CRC-7x7 + x3 + 1 (use: telecom systems, MMC)CRC-8-x8 + x7 + x3 + x2 + 1 (use: 1-Wire bus)CCITTCRC-15-CANx15 + x14 + x10 + x8 + x7 + x4 + x3 + 1CRC-16-x16 + x12 + x5 + 1 (X.25, V.41, Bluetooth, PPP, CCITTIrDA, BACnet; known as “CRC-CCITT”)CRC-16-IBMx16 + x15 + x2 + 1 (XMODEM, USB, many others; also known as “CRC-16”)CRC-24-x24 + x23 + x18 + x17 + x14 + x11 + x10 + x7 + x6 + Radix-64x5 + x4 + x3 + x + 1CRC-32-x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + MPEG2x7 + x5 + x4 + x2 + x+ 1CRC-32-IEEEx32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + 802.3x7 + x5 + x4 + x2 + x + 1 (V.42)CRC-64-ISOx64 + x4 + x3 + x + 1 (use: ISO 3309)CRC-64-x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + ECMA-182x45 + x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 +x29 + x27 + x24 + x23 + x22 + x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1 (as describedin ECMA-182 p.63)
As illustrated in Table 1, many leading technology companies, and standards bodies, such as USB, IEEE, and ITU, etc. have adopted various implementations of CRC calculations by alternative values of polynomials. The polynomial must be chosen to maximize the error detecting capabilities while minimizing overall collision probabilities. For instance, the most commonly used polynomial lengths are 9 bits, 17 bits, 33 bits, and 65 bits, or as commonly known CRC-8, CRC-16, CRC-32 and CRC-40, CRC-64 respectively.
A CRC building block uses a generator polynomial to build a CRC module, where the CRC module consists of at least two CRC circuits. The modularity of a CRC design allows a larger CRC module constructed from multiple CRC circuits, such that wider data, e.g., 64 bits, 128 bits, may be accommodated. In an example, a designer may incorporate added flexibility in a CRC design by having a programmable generator polynomial as an input design parameter. The above example allows the same CRC circuit to be used to support different standards or user defined generator polynomials.